package com.lecode.tree;

import com.lecode.link.Link;

import javax.xml.soap.Node;
import java.util.*;
import java.util.concurrent.BlockingQueue;
import java.util.concurrent.LinkedBlockingQueue;
import java.util.concurrent.ThreadPoolExecutor;

public class Tree {

	
//二叉树
class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;
	TreeNode(int val, TreeNode left, TreeNode right) {
		this.val = val;
		this.left = left;
		this.right = right;
	}

	TreeNode(int val) {
		this.val = val;
	}
 }
	
	/**
	 * 二叉树的中序遍历：左节点、根节点、右节点
	 * 
	 * 递归
	 * @param root
	 * @return
	 */
	public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
        middleOrder(list, root);
        return list;
    }
	
	public void middleOrder(List<Integer> list, TreeNode node){
		if(node != null){
			if(node.left != null){
				middleOrder(list, node.left);
			}
			list.add(node.val);
			if(node.right != null){
				middleOrder(list, node.right);
			}
		}
	}

	/**
	 * 513、给定一个二叉树，在树的最后一行找到最左边的值。
	 *
	 * bfs：广度遍历二叉树
	 * @param root
	 * @return
	 */
	public int findBottomLeftValue(TreeNode root) {
		int result = root.val;
		Queue<TreeNode> queue = new LinkedList<TreeNode>();
		queue.add(root);
		while (!queue.isEmpty()){
			TreeNode curr = queue.poll();
			if (curr.right != null) {result = curr.right.val; queue.add(curr.right);}
			if (curr.left != null) {result = curr.left.val; queue.add(curr.left);}
		}
		return result;
	}

	/**
	 * dfs:深度遍历，查询
	 * 同一层只取最左边的值
	 */
	int[] botto = new int[]{0, -1};
	public void dfsBottomLeftValue(TreeNode root, int depth){
		if (root == null)
			return;

		if (depth > botto[1]){
			botto[0]  = root.val;
			botto[1] = depth;
		}
		dfsBottomLeftValue(root.left, depth + 1);
		dfsBottomLeftValue(root.right, depth + 1);
	}

	/**
	 * 236、求二叉树的最近公共祖先
	 *
	 * 使用后序遍历(左右根：从下往上)
	 * @param root
	 * @param p
	 * @param q
     * @return
     */
	public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
		if (root == null) return null;
		if (root == p || root == q) return root;
		TreeNode left = lowestCommonAncestor(root.left, p, q);
		TreeNode right = lowestCommonAncestor(root.left, p, q);

		if (left != null && right != null)
			return root;
		if (left == null && right == null)
			return null;
		return left == null ? right: left;
	}

	public void aa(TreeNode node){
		if (node == null) return;

		System.out.print(node.val);
		aa(node.left);
		aa(node.right);
	}

	/**
	 * 二叉树的序列化
	 * @param root
	 * @return
     */

	public String serialize(TreeNode root) {
		StringBuffer bf = new StringBuffer();
		traverse(root, bf);
		return bf.toString();
	}

	public void traverse(TreeNode root,StringBuffer bf){
		if (root == null){
			bf.append("#").append(",");
			return;
		}
		bf.append(String.valueOf(root.val)).append(",");
		traverse(root.left, bf);
		traverse(root.right, bf);
	}

	/**
	 * 二叉树的反序列化
	 * @param data
	 * @return
     */
	public TreeNode deserialize(String data) {
		LinkedList<String> nodes = new LinkedList();
		for (String node: data.split(",")){
			nodes.add(node);
		}
		return traverse2(nodes);
	}

	private TreeNode traverse2(LinkedList<String> nodes){
		if (nodes.isEmpty()) return null;

		String firstNode = nodes.getFirst();
		nodes.removeFirst();
		if (firstNode.equals("#")) return null;
		TreeNode treeNode = new TreeNode(Integer.valueOf(firstNode));
		treeNode.left = traverse2(nodes);
		treeNode.right = traverse2(nodes);
		return treeNode;
	}


	public void bb(TreeNode node){
		if (node == null) return;
		aa(node.left);
		aa(node.right);
		System.out.print(node.val);
	}
}
